Sparse Index

在数据主键有序的基础上，只为少部分数据建立索引，从而在查询时能够圈定出大致的范围，再在范围内利用适当的查找算法找到目标数据。

空间占用小，查询相对慢

Sparse Index in Kafka

单个Kafka的TopicPartition中，消息数据会被切分成段（segment）来存储，扩展名为.log。log文件的切分时机由大小参数log.segment.bytes（默认值1G）和时间参数log.roll.hours（默认值7天）共同决定。数据目录中存储的部分文件如下。

.
├── 00000000000190089251.index
├── 00000000000190089251.log
├── 00000000000190089251.timeindex
├── 00000000000191671269.index
├── 00000000000191671269.log
├── 00000000000191671269.timeindex
......

log文件的文件名都是64位整形，表示这个log文件内存储的第一条消息的offset值减去1（也就是上一个log文件最后一条消息的offset值）。

每个log文件都会配备偏移量索引（index）和时间戳索引（timeindex）文件，且均为稀疏索引。由于索引文件不大，易于mmap，存取效率很高。

index 文件中存储的是offset值与对应数据在log文件中存储位置的映射
timeindex 文件中存储的是时间戳与对应数据offset值的映射

~ kafka-run-class kafka.tools.DumpLogSegments --files /data4/kafka/data/ods_analytics_access_log-3/00000000000197971543.index
Dumping /data4/kafka/data/ods_analytics_access_log-3/00000000000197971543.index
offset: 197971551 position: 5207
offset: 197971558 position: 9927
offset: 197971565 position: 14624
offset: 197971572 position: 19338
offset: 197971578 position: 23509
offset: 197971585 position: 28392
offset: 197971592 position: 33174
offset: 197971599 position: 38036
offset: 197971606 position: 42732
......

~ kafka-run-class kafka.tools.DumpLogSegments --files /data4/kafka/data/ods_analytics_access_log-3/00000000000197971543.timeindex
Dumping /data4/kafka/data/ods_analytics_access_log-3/00000000000197971543.timeindex
timestamp: 1593230317565 offset: 197971551
timestamp: 1593230317642 offset: 197971558
timestamp: 1593230317979 offset: 197971564
timestamp: 1593230318346 offset: 197971572
timestamp: 1593230318558 offset: 197971578
timestamp: 1593230318579 offset: 197971582
timestamp: 1593230318765 offset: 197971592
timestamp: 1593230319117 offset: 197971599
timestamp: 1593230319442 offset: 197971606
......

以index文件为例，查找 offset=197971577 的消息流程是：

通过二分查找，在index文件序列中，找到包含该offset的文件（00000000000197971543.index）
通过二分查找，在上一步定位到的index文件中，找到该offset所在区间的起点（197971592）
从上一步的起点开始顺序查找，直到找到目标offset。